﻿// See https://aka.ms/new-console-template for more information

using System.Diagnostics;

class SolutionMain
{
    void main()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();

        Solution Solution = new Solution();
        IList<int> List1 = new List<int>();
        for (int i = 0; i < 15; i++)
        {
            List1.Add(Solution.getSize(i));
        }


        Console.WriteLine(List1[List1.Count - 1]);

        sw.Stop();
        Console.WriteLine($"程序耗时：{sw.ElapsedMilliseconds}ms.");

        Console.ReadKey();
    }
}




class Solution
{
    private int n;
    private int solutionsCount; // 直接记录解的数量，避免存储棋盘

    public int getSize(int n)
    {
        this.n = n;
        this.solutionsCount = 0;
        Backtrack(0, 0, 0, 0);
        return solutionsCount;
    }

    // 使用三个位掩码分别表示列、主对角线、副对角线的占用情况
    private void Backtrack(int row, int colMask, int diag1Mask, int diag2Mask)
    {
        if (row == n)
        {
            solutionsCount++;
            return;
        }

        // 计算可用列（二进制中1表示可用）
        int availablePositions = ((1 << n) - 1) & ~(colMask | diag1Mask | diag2Mask);

        while (availablePositions != 0)
        {
            // 获取最低位的1（即下一个可用列）
            int position = availablePositions & -availablePositions;

            // 递归处理下一行
            Backtrack(
                row + 1,
                colMask | position,
                (diag1Mask | position) << 1,
                (diag2Mask | position) >> 1
            );

            // 清除最低位的1，继续处理下一个可用列
            availablePositions &= availablePositions - 1;
        }
    }
}






